1. Field of the Invention
The present invention relates to a multiplier device and to a shifter.
2. Description of the Prior Art
With the spreading of digital signal processing, a need for multiplier devices which multiply digital signals has arisen.
Conventionally, when multiplying two digital signals each of which representing a number value, the multiplication is performed as follows. Assume A to represent the multiplicand and B to represent the multiplier, and assume further, for example only, that A and B, respectively, are in a 4 bit representation (generally, a n-bit representation) (a bit being also referred to as digit).
For multiplying (in decimal system) A=11 by B=7 (which yields 77 in decimal notation), the following has to be effected if A, B are binary signals.
For each bit of the multiplier, the value of the multiplicand is to be shifted by a number of bits, which number of bits corresponds to the significance of the bit of the multiplier. That is, for the least significant bit (representing 20), a zero shift of the multiplicand has to be effected, while for the most significant bit out of n bits (representing 2n−1), a shift by (n−1) bits has to be effected. Also, as shown below, the thus shifted multiplicand values will have to be added to form the result.

Stated in other words, the multiplier bits serve to control the respective shifting (which corresponds to a multiplication by a respective power of two in binary representation) of the multiplicand, and the shifted multiplicands are to be added.
In the field of digital signal processing, for example in the field of digital filtering, binary data are also represented as Sum-Of-Powers-Of-Two (SOPOT). A number represented with Sum-Of-Powers-Of-Two (SOPOT) can be a Canonic Signed Digit (CSD), in order to perform the multiplications needed for example in filtering operations. Other Sum-Of-Powers-Of-Two (SOPOT) representations can be the signed digit (SD) representations, the Minimum Signed Digit (MSD) representation, which are explained herein below.
In Canonic Signed Digit code, values of 1, 0, and −1 are used as digits to represent the value, whereas the binary code uses only 0 and 1. In an ordinary binary number, the average number of non-zero digits is larger than in CSD coded numbers, so that the CSD coded number has a minimum of non-zero terms.
For example, the following table shows a correspondence between a binary coded number of n=4 bits (the example represents values of 0 to 15) and the corresponding CSD coded number. Correspondences of decimal numbers 16 and 17 for binary and CSD representation are also shown.
DecimalBinaryCSD0000000000100010000120010000103(= 4 − 1)00110010-1401000010050101001016(= 8 − 2)0110010-107(= 8 − 1)01110100-1810000100091001010011010100101011(= 16 − 4 − 1)101110-10-112(= 16 − 4)110010-10013(= 16 − 4 + 1)110110-10114(= 16 − 2)1110100-1015(= 16 − 1)11111000-1161000010000171000110001. . .etc.
In a case of negative binary numbers, this example may be different. It should be kept in mind that with CSD code representation, the number is only approximated. Apparently, as derivable from the above example, when using CSD representation, with a maximum number of non-zero bits, the decimal numbers may be represented.
Generally, in CSD coded numbers, no non-zero terms can be placed adjacent to each other, so that a terms of 1 and/or −1 are always to be spaced by a term of 0.
Also, the above example was given with reference to positive integer values only. Generally, a CSD presentation of any number (X) can be given by representing the number in sums and differences of powers of two as follows:
      X    =                  ∑                  i          =                      -            ∞                                    i          =                      +            ∞                              ⁢                          ⁢                        g          i                *                  2          i                      ,          ⁢            with      ⁢                          ⁢              g        i              ∈          {                        -          1                ,        0        ,        1            }      
Thus, the above example has been chosen such that only positive values of i are used.
The number of additions (NA) needed in a multiplication is then NA=(L−1), wherein L is the number of non-zero terms in the CSD presentation.
For the decimal value of “7”, with CSD code representation in comparison to binary representation, the number of non-zero terms is reduced from three to two, while also, the number of necessary shift operations is reduced (from two shifts for the middle two bits in binary representation to only one shift operation for the most significant bit in CSD representation, since for the least significant bit, no shifting is required (shift by zero).)
Thus, referring back to the above example of multiplying A*B (11*7), this corresponds to the subtraction of “one times A” from “eight times A” when using CSD representation of the multiplier. A subtraction, however, corresponds to the addition of the 2's complement of the value to be subtracted. (The 2's complement is formed by inverting each bit of the value to be subtracted (1's complement) and then adding just binary “1” thereto.)
Thus, when making use of the CSD representation, a multiplier device which is a part in digital designs, which part consumes the most area on a semiconductor device chip, is replaced by a certain number of adders. The number of adders is dependent on the accuracy of the presentation of the multiplier which in turn is dependent on the number of non-zero terms in the CSD code representation.
The multiplication by a power of two (i.e. 20, 21, . . . , 2n) is usually performed by shifting the multiplicand (in binary and/or 2's complement) format either to the left by a corresponding number of bits (as explained above) for multiplication, or to the right in case of division.
Generally, a number that is represented with Sum-Of-Powers-Of-Two (SOPOT) is represented in a so-called Signed Digit representation wherein the sign of the different power of two can have a value out of the set of values 1, 0, −1. Minimum Signed Digit (MSD) representation is the format, in which the number is represented with a minimum number of non-zero terms. There can be many different MSD representations of a same number. Canonic Signed Digit (CSD) representation is always one of the possibilities of MSD representation, while CSD is the format, in which there is a restriction such that the occurrence of adjacent non-zero signals is not allowed (thus, there are no adjacent non-zero digits in CSD representation). For example, assume a number of decimal “3”, which can be represented in
SDMSDCSDas follows:1-1-110011010-11-10-1010-10011010-1
In cases, in which the multiplier has a fixed value and is thus known beforehand, the shifts can be realized by wiring and without any extra hardware (logic circuits).
However, this limits the applicability of the multiplier device to multiplications by only the fixed multiplier value.
For increasing a field of applicability of a multiplier to variable multiplier values, arrangements have been conceived, according to which the shift amounts can be altered.
FIG. 1 shows a prior art arrangement of a shifting means usable in a multiplier device. The shifting means effects variable shift amounts for variable control signals, for example in a binary and/or CSD representation. A control signal can be a multiplier in case of applying the shifter in a multiplier device. At least, the control signal is derivable from the multiplier.
As shown in FIG. 1, the multiplicand denoted by X is supplied to the shifting means. The multiplicand is branched, with the number of branches corresponding to the number of bits of the multiplier (not shown as a separate signal (control signal) in FIG. 1). As shown in FIG. 1, the multiplicand X is branched to eight branches, with a respective branch of the multiplicand's signal X (duplicate of X) being subjected to a respective fixed shift of a value between zero and seven. The shifting is performed by a shifting element (not shown) realized by a wiring which shifts the supplied signal X by the provisioned (predetermined) shift amount.
A respective pair of shifted values of the signal X is supplied to a first stage of multiplexers MUX (2:1 multiplexer). One of the shifted signals is selected by a control signal (not shown) supplied to the multiplexer.
Each output of one of the first stage multiplexers is supplied to a respective multiplexer of a second stage of multiplexers MUX (2:1 multiplexers). Since the multiplexers are 2:1 multiplexers in the example of FIG. 1, respective two output signals of a first stage are supplied to a multiplexer of the second stage. One of the input signals to a respective second stage multiplexer is selected by a control signal (not shown) supplied to the multiplexer.
Each output of one of the second stage multiplexers is supplied to a multiplexer of a third stage of multiplexers MUX (2:1 multiplexers). One of the input signals to a respective third stage multiplexer is selected by a control signal (not shown) supplied to the multiplexer to be output (labeled Y in FIG. 1). Note that as shown in FIG. 1, the third stage of multiplexers contains a single multiplexer only.
As the control signal for controlling the multiplexers of the first through third stage, either the bits of the multiplier are directly used or the control signal bits are derived from the bits of the multiplier, and applied thereto in a manner such that the multiplicand X is shifted by a value corresponding to the significance of a respective bit of the multiplier being currently processed. Stated in other words, assuming that a first bit has the significance of zero (least significant bit LSB) and an eighth bit has a significance of seven (most significant bit MSB), then if the bit no. 5 of the multiplier is processed, this fifth bit has a significance of “four”. Hence, the multiplexer stages are controlled such that at the output Y of the shifting means the signal X shifted by an mount of four bits is output.
Apparently, such a shifting means as shown in FIG. 1 requires numerous logic circuits and multiplexer devices for realizing a desired shift amount.
Still further, for effecting multiplication operations, such shifted values of the multiplicand have to be added, as explained above with reference to the example of the multiplication operation.
FIG. 2 of the drawings shows an arrangement of adders for summing those shifted values. In the example shown, in order to keep the drawing simple, it has been assumed that the multiplier is only a four bit multiplier.
Thus, the multiplicand X is supplied to four shifting means “Shifter”. Each shifting means may be constituted and subjected to a control by the multiplier as described with reference to FIG. 1.
At the output of the shifting means, respective outputs Y0, Y1, Y2, and Y3 are output which denote signal X shifted by zero (Y0), signal X shifted by one (Y1), signal X shifted by two (Y2), and signal X shifted by zero (Y3), respectively.
These shifting means output signals are grouped to pairs and supplied to respective adder means denoted by “+”. The adder means are arranged to perform an addition in parallel since Y0 and Y1 are added by one of the adder means, while simultaneously Y2 and Y3 are added by another one of the adder means.
The thus obtained partial additions are supplied to a further adder means of a subsequent adder stage, are added and output as a final addition result (Z).
Thus, also such a multiplier device using parallel addition requires numerous adder means and numerous shifting means, that is a bulky hardware, in order to be suitable for performing the multiplication by a variable multiplier.
Further prior art is known, for example, from the publication “A Systematic Approach For Design Of Digit-Serial Signal Processing Architectures” by K. K. Parhi, in IEEE Transactions on Circuits and Systems, Vol. 38, No. 4, April 1991. This document presents a systematic unfolding technique to transform bit-serial architectures into equivalent digit-serial ones. However, in order to accomplish this goal, functionally correct control circuits have to be generated and implemented, thereby leading to an increased amount of (control) hardware.
W. J. Oh and Y. H. Lee present in their article “Implementation Of Programmable Multiplierless FIR Filters With Powers-Of-Two Coefficients” in IEEE Transactions On Circuits and Systems-II: Analog And Digital Signal Processing, Vol. 42, No. 8, August 1995, a possibility to implement shorter shifters. However, the arrangement of multiplier devices is not specifically concerned.
Duan, Ko, and Daneshrad discuss in their article “Versatile Beamforming ASIC Architecture For Broadband Fixed Wireless Access”, in IEEE Custom Integrated Circuits Conference, 1999, that programmable CSD multiplication is usually implemented using shifters and multiplexers, while their examination of CSD properties revealed that as discussed by Oh, Lee cited above, the number of shifters and multiplexers can be reduced by dividing the shift operation into a pre-shift and hardwired shift, thereby resulting in further complexity reduction.
However, studies of the present inventors revealed that the achievable complexity reductions are still not optimum.
The same holds for the above authors' (Duan et al.) publication “A Highly Versatile Beamforming ASIC For Application In Broad-Band Fixed Wireless Access Systems” in IEEE Journal Of Solid-State Circuits, Vol. 35, No. 3, March 2000.
Khoo, Kwentus and Willson propose in “A Programmable FIR Digital Filter Using CSD Coefficients”, in IEEE Journal of Solid-State Circuits, Vol. 31, No. 6, June 1996, a coefficient multiplier adopting a two-level transmission gate multiplexer network for selecting appropriate hardwired pre-shift data. This, however, causes considerable delay, which is suggested to be compensated by an (additional) pipeline register. This, however, does not support the complexity to be reduced to a minimum.
Several types of multipliers are presented by Chang, Satyanarayana and Parhi in “Systematic Design Of High-Speed and Low-Power Digit-Serial Multipliers”, in IEEE Transactions On Circuits And Systems-II: Analog And Digital Signal Processing, Vol. 45, No. 12, December 1998. However, processing of a multiplier being represented in CSD format is not considered.
Also, a CSD multiplier device requiring still a considerable amount of silicon area is known from U.S. Pat. No. 4,967,388.
A further programmable CSD multiplier is disclosed in U.S. Pat. No. 5,262,974. However, several programmable shift paths and a corresponding plurality of adders are provided for summing these outputs. Hence, also this prior art arrangement requires quite a bulky hardware which consumes quite significant area when implemented on a silicon chip.
In summary, implementing flexibility to achieve multiplication by a variable multiplier requires additional hardware, i.e. logic circuits.
In consequence, such arrangements are quite bulky and consume lots of semiconductor chip area, which is undesired in view of the aim to miniaturize IC chip designs. Also, the costs for such devices increase with an increase in the consumed chip area.